﻿/*
1007 素数对猜想 (20 分)
让我们定义d
​n
​​ 为：d
​n
​​ =p
​n+1
​​ −p
​n
​​ ，其中p
​i
​​ 是第i个素数。显然有d
​1
​​ =1，且对于n>1有d
​n
​​ 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N(<10
​5
​​ )，请计算不超过N的满足猜想的素数对的个数。

输入格式:
输入在一行给出正整数N。

输出格式:
在一行中输出不超过N的满足猜想的素数对的个数。

输入样例:
20
输出样例:
4
*/

#pragma warning(disable: 4267)
#pragma warning(disable: 4996)
#pragma warning(disable: 6031)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

namespace B1007 {
int main();

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

bool isPrime(unsigned long n) {
	if (n <= 3) {
		return n > 1;
	}
	else if (n % 2 == 0 || n % 3 == 0) {
		return false;
	}
	else {
		for (unsigned short i = 5; i * i <= n; i += 2) {
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}
}

int primeArray[100000] = {};
int founded[100001] = {};

int main() {
	freopen("D:/Develop/GitRepos/MOOC/浙江大学/数据结构/201906/PTA(Basic)/data/1007.txt", "r", stdin);
	int n, i, j;
	int m = 0;

	scanf("%d", &n);
	for (i = 2; i <= n; i++) {				//不超过n, 读题有漏洞
		if (founded[i])
			continue;
		if (isPrime(i))
			primeArray[m++] = i;
		for (j = i * 2; j < n; j += i)
			if (0 == founded[j])
				founded[j] = 1;
	}

	int k = 0;
	for (i = 1; i < m; i++)
	{
		if (primeArray[i] - primeArray[i - 1] == 2)
			k++;
	}

	printf("%d %d\n", m, k);

	return 0;
}
}

int main_B1007() {
	return B1007::main();
}